class Solution 
{
public:
    int row, col;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    bool _exist(vector<vector<char>>& board, vector<vector<bool>>& vvb, string& word, int i, int j, int pos)
    {
        if(i < 0 || j < 0 || i >= row || j >= col) return false;
        if(pos == word.size()-1) return true;
        vvb[i][j]  = true;

        for(int k=0; k<4; ++k)
        {
            if(i+dx[k] < 0 || i+dx[k] >= row || j+dy[k] < 0 || j+dy[k] >= col) continue;

            if(board[i+dx[k]][j+dy[k]] == word[pos+1] && vvb[i+dx[k]][j+dy[k]] == false)
            {
                bool ret = _exist(board, vvb, word, i+dx[k], j+dy[k], pos+1);
                if(ret) return true;
            }
        }

        vvb[i][j] = false;
        return false;
    }

    bool exist(vector<vector<char>>& board, string word) 
    {
        row = board.size(), col = board[0].size();
        vector<vector<bool>> vvb(row, vector<bool>(col, false));

        for(int i=0; i<row; ++i)
        {
            for(int j=0; j<col; ++j)
            {
                if(board[i][j] == word[0])
                {
                    bool ret = _exist(board, vvb, word, i, j, 0);
                    if(ret) return true;
                }
            }
        }

        return false;
    }
};